package leetcode_DFS;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 最大人工岛
 * 算法：深度优先搜索
 * 给每块岛屿标号, 遍历 0, 将 0 变成 1, 得出最大面积
 *
 * @author yezh
 * @date 2023/2/7 21:30
 */
public class _827 {

    public int largestIsland(int[][] grid) {
        int m = grid.length, n = grid[0].length, sign = 2;
        Map<Integer, Integer> map = new HashMap<>(8);
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) {
                int area = dfs(i, j, grid, sign);
                if (area == m * n) return area;
                map.put(sign++, area);
            }
        int ans = 0;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (grid[i][j] == 0) {
                    int tmp = 1;
                    Set<Integer> set = new HashSet<>(4);
                    if (i + 1 < m) set.add(grid[i + 1][j]);
                    if (i - 1 >= 0) set.add(grid[i - 1][j]);
                    if (j + 1 < n) set.add(grid[i][j + 1]);
                    if (j - 1 >= 0) set.add(grid[i][j - 1]);
                    for (int v : set) tmp += map.getOrDefault(v, 0);
                    if (tmp > ans) ans = tmp;
                }
        return ans;
    }

    int dfs(int i, int j, int[][] grid, int sign) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length) return 0;
        if (grid[i][j] != 1) return 0;
        grid[i][j] = sign;
        int area = 0;
        area += dfs(i + 1, j, grid, sign);
        area += dfs(i, j + 1, grid, sign);
        area += dfs(i - 1, j, grid, sign);
        area += dfs(i, j - 1, grid, sign);
        return area + 1;
    }

}
